package leetcode每日一题.leetcode20212;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 1. 问题描述
 *      外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。
 *      字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：
 *      单词 word 中包含谜面 puzzle 的第一个字母。
 *      单词 word 中的每一个字母都可以在谜面 puzzle 中找到。
 *      例如，如果字谜的谜面是 "abcdefg"，那么可以作为谜底的单词有 "faced", "cabbage",
 *      和 "baggage"；而 "beefed"（不含字母 "a"）以及 "based"（其中的 "s" 没有出现在谜面中）都不能作为谜底。
 *      返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words
 *      中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。
 *
 * 2. 算法分析
 *      1. 暴力
 *
 *      2.
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q026_猜字谜 {

    /**
     * 暴力法  时间复杂度为O(n^3) 超出leetcode的平台的测试时间
     * @param words
     * @param puzzles
     * @return
     */
    public List<Integer> findNumOfValidWords1(String[] words, String[] puzzles) {
        List<Integer> res = new ArrayList<>();
        for(String puzzle : puzzles) {
            int temp = 0;
            for(String word : words) {
                if(isAnswer(word,puzzle)) {
                    temp++;
                }
            }
            res.add(temp);
        }
        return res;
    }
    public boolean isAnswer(String word,String puzzle) {
        char[] charArrayWord = word.toCharArray();
        char[] charArrayPuzzle = puzzle.toCharArray();
        int[] freqWord = new int[26];
        int[] freqPuzzle = new int[26]; // 统计puzzle，需要提前初始化，固定不变的
        for(char ch : charArrayPuzzle) {
            freqPuzzle[ch - 'a']++;
        }
        for(char ch : charArrayWord) {
            freqWord[ch - 'a']++;
        }
        if(freqWord[charArrayPuzzle[0] - 'a'] == 0) {
            return false;
        }
        for(char ch : charArrayWord) {
            if(freqPuzzle[ch - 'a'] == 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 暴力   稍微优化了一点，简化了代码的编写，但是时间复杂度依旧是O(n^3) 超出时间限制
     * @param words
     * @param puzzles
     * @return
     */
    public List<Integer> findNumOfValidWords2(String[] words, String[] puzzles) {
        List<Integer> res = new ArrayList<>();
        for(String puzzle : puzzles) {
            int curCount = 0;
            char[] charArrayPuzzle = puzzle.toCharArray();
            int[] freqPuzzle = new int[26];
            for(char ch : charArrayPuzzle) {
                freqPuzzle[ch - 'a']++;
            }
            for(String word : words) {
                char[] charArrayWord = word.toCharArray();
                int[] freqWord = new int[26];
                int right = 0;
                while(right < charArrayWord.length) {
                    //  如果word右窗口的字符没有出现在puzzle中，直接退出循环，因为肯定不符合
                    if(freqPuzzle[charArrayWord[right] - 'a'] == 0) {
                        break;
                    }
                    // 如果出现，更新word的频数数组，然后右窗口移动一位
                    freqWord[charArrayWord[right] - 'a']++;
                    right++;
                    if(right == charArrayWord.length && freqWord[charArrayPuzzle[0] - 'a'] != 0) {
                        curCount++;
                    }
                }
            }
            res.add(curCount);
        }
        return res;
    }

    /**
     * 看的leetcode上别人给出的解答，但是没有看懂思路，待定吧
     * @param words
     * @param puzzles
     * @return
     */
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        HashMap<Integer, Integer> wordMap = new HashMap<>();
        for (String word : words) {
            int bit = getBit(word);
            wordMap.put(bit, wordMap.getOrDefault(bit, 0) + 1);
        }

        ArrayList<Integer> answer = new ArrayList<>();
        for (String puzzle : puzzles) {
            int bit = getBit(puzzle);

            int first = puzzle.charAt(0) - 'a';
            int t = bit, cnt = 0;
            while (t > 0) {
                if (((1 << first) & t) != 0 && wordMap.getOrDefault(t, 0) > 0) {
                    cnt += wordMap.get(t);
                }
                t = (t - 1) & bit;
            }
            answer.add(cnt);
        }
        return answer;
    }
    private int getBit(String str) {
        char[] arr = str.toCharArray();
        int res = 0;
        for (char c : arr) {
            int t = c - 'a';
            res = res | (1 << t);
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(0x1);
    }
}
